/*
Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (!head || !k) return head;
        int len = 1; ListNode *ptr = head;
        for (; ptr->next; ptr = ptr->next) len++;
        k = k % len;
        if (!k) return head;
        // point tail to head
        ptr->next = head;
        // locate new tail
        for (int i = len-k; i>0; i--) ptr = ptr->next;
        ListNode *newhead = ptr->next; // new head
        ptr->next = NULL;
        return newhead;
    }
};

#if 0
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (!head) return head;
        int len = 0; ListNode *ptr;
        for (ptr = head; ptr; ptr = ptr->next) len++;
        if (len <= k) k %= len;
        if (k <= 0) return head;
        // Locate position before rotation
        ListNode *p1 = head, *p2 = head;
        while (k--) p2 = p2->next;
        while (p2->next) {
            p1 = p1->next;
            p2 = p2->next;
        }
        p2->next = head;
        head = p1->next;
        p1->next = NULL;
        return head;
    }
};
#endif
